COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00022 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex[106,phy]
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a66.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Chapter 2: Definition of machine, standardize, simulate, \dots\hfil}

Computers and computer programs contain components that can hold information,
test~it, and operate on~it. For example, a~counter can hold an integer;
the counter
can test whether it contains zero; and it can increase or decrease its
content by one. A~clock holds an integer, and at every step increases its
content by one. Other such components are paper and magnetic tapes, random
access memories, pushdown stacks, lists, and queues. We will consider
certain such components, called {\it devices}, that are amenable to study with
the tools of mathematics.

A device has a {\it carrier}, the set of the values it may contain. A~{\it state\/}
of the device is an element of the carrier. The carrier of a counter,
for example, might be~{\bf Z}, the set of all integers, or~{\bf N}, the set
of all natural numbers (non-negative integers). 
A~device  has a {\it repertory},
a~set of partial functions on the carrier. For a counter with carrier~{\bf N},
the repertory might include ${\tt INCREMENT}(x)=x+1$, ${\tt DECREMENT}(x)=x-1$
(defined only for $x≠0$), ${\tt ZERO}(x)=x$ (defined only for $x=0$), and
${\tt NONZERO}(x)=x$ (defined only for $x≠0$). The repertory of a device
normally includes ${\tt NOOP}(x)=x$, an operation that does nothing,
but the example of a clock shows why {\tt NOOP} might not be in the
repertory. Operations in the repertory that are subsets of the identity
function, like {\tt ZERO} and {\tt NONZERO}, are called {\it tests}.
Ordinarily the union of two tests, or the complement of a test, is also a
test in the repertory.

A {\it machine\/} is a finite set of devices. For example, what is called
a two-counter transducer consists of a {\it control}, which has a finite
carrier; two counters,
each with its own repertory of {\tt INCREASE}, {\tt DECREASE}, etc.; and
an {\it input\/} and an {\it output}, each of which has as its carrier 
the set of strings over some alphabet.

A {\it configuration\/} of a machine is a correspondence between each
device and a state. The set of configurations is therefore the cartesian
product of the carriers. When a machine goes to work, it~passes through
a finite or infinite sequence of configurations.

An {\it instruction\/} for a machine is a correspondence between each device
and an operation from its repertory. An instruction can be applied to a
configuration if, for each device, the operation in the instruction can
be applied to the state in the configuration. If a machine has devices
$D↓1$, $D↓2$, and~$D↓3$, in respective states $x↓1$, $x↓2$, $x↓3$, then the
instruction ($f↓1$, $f↓2$, $f↓3$) changes the current configuration 
($x↓1$, $x↓2$, $x↓3$) into its sequel $\bigl(f↓1(x↓1), f↓2(x↓2), f↓3(x↓3)\bigr)$,
provided all are defined. Every instruction is a partial function on the
configurations of a machine.

For each device, there is a set of {\it initial states\/}; many devices have
only one initial state, but an {\it input\/} device may have many. Similarly,
there is a set of {\it final states}. Correspondingly, an {\it initial
configuration\/} consists of initial states, and a {\it final configuration\/}
consists of final states. A~{\it program\/} is a finite set of instructions.
For the moment we consider only programs where at most one instruction
applies to a configuration, and no instruction applies to a final configuration.
Then, starting with any initial configuration, there is at most one sequence
of configurations obtained by repeatedly applying instructions from the program.
Such a sequence of configurations, either infinite or ending in a final
configuration, is called a {\it trace\/} of the program operating on the
initial configuration; the sequence of instructions applied is called
a {\it computation\/} of the machine.

\vfill\eject

For example, consider this flowchart:

\bigskip
$$\vcenter{\halign{\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\quad%
&\hfil#\hfil\cr
&{\tt START}\cr
\noalign{\bigskip}
&$x←0$\cr
\noalign{\bigskip}
\noalign{\bigskip}
&2\cr
\noalign{\bigskip}
&&{\tt EOF}\cr
&{\tt READ} $C$&&&6&&$x=0$ ?\cr
\noalign{\bigskip}
&3&&&&$Y$&&$N$\cr
\noalign{\bigskip}
&$C=?$&&&&7&&8\cr
\noalign{\bigskip}
$a$&&$b$&&&{\tt PRINT}&&{\tt PRINT}\cr
&&&&&``{\tt{ACCEPT}}''&&``{\tt{REJECT}}''\cr
\noalign{\bigskip}
4&&5&&&&9\cr
\noalign{\bigskip}
$x←x+1$&&$x←x-1$&&&&{\tt HALT}\cr}}$$

\bigskip
\bigskip
A machine that could perform this algorithm has a control device with 
states~1 to~9; a~counter with carrier~{\bf Z}; and an input device that
holds a string (file) of $a$'s and~$b$'s. A~program for this machine to
carry out the algorithm is
$$\vcenter{\halign{\quad\hfil#\hfil\qquad&#\hfil\qquad&#\hfil\qquad&#\hfil\quad\cr
{\tt CONTROL}&{\tt INPUT}&{\tt COUNTER}&comments\cr
\noalign{\medskip}
\noalign{\hrule}
\noalign{\medskip}
$\langle 1,2\rangle\,,$&{\tt NOOP},&{\tt NOOP}&Initial state of counter is zero\cr
$\langle 2,4\rangle\,,$&{\tt SCAN} $a$,&{\tt NOOP}&Variable $C$ not needed\cr
$\langle 4,2\rangle\,,$&{\tt NOOP},&{\tt INCREMENT}&Counter contains $x$\cr
$\langle 2,5\rangle\,,$&{\tt SCAN} $b$,&{\tt NOOP}\cr
$\langle 5,2\rangle\,,$&{\tt NOOP},&{\tt DECREMENT}\cr
$\langle 2,6\rangle\,,$&{\tt EOF},&{\tt NOOP}\cr
$\langle 6,7\rangle\,,$&{\tt NOOP},&{\tt ZERO}\cr
$\langle 6,8\rangle\,,$&{\tt NOOP},&{\tt NONZERO}\cr}}$$
where 1 is the initial control state, and 7 is the final control state. The
initial and final states of the input are $\{a,b\}↑{\ast}$, although
this particular program only halts when the state of the input is the
empty string. The initial state of the counter is zero, the final states
are~{\bf Z}.

A much shorter program that does not correspond to any traditional flowchart,
but meets the definitions used here, is:
$$\vcenter{\halign{\hfil#\hfil\qquad&#\hfil\qquad&#\hfil\cr
$\langle 2,2\rangle\,,$&{\tt SCAN} $a$,&{\tt INCREASE}\cr
$\langle 2,2\rangle\,,$&{\tt SCAN} $b$,&{\tt DECREASE}\cr
$\langle 2,7\rangle\,,$&{\tt EOF},&{\tt ZERO}\cr}}$$
Rather than use traditional flowcharts, we will present programs pictorially
by labeled digraphs, with control states as vertices. An instruction with
$\langle i,j\rangle$ as its control operation is shown as an arc
from~$i$ to~$j$, labeled with all other operations of the instruction
except {\tt NOOP}s. Initial control states are marked by~$\Rightarrow$,
accepting control states by a plus sign. The two programs above are presented
by the following graphs:

\bigskip
\bigskip
$$\vcenter{\halign{%
$\hfil#\hfil$\quad%arrow
&\hfil#\hfil\qquad\qquad%number
&\hfil#\hfil\quad%number
&\hfil#\hfil\qquad%description
&\hfil#\hfil\quad%number
&\hfil#\hfil\qquad%description
&\hfil#\hfil\qquad%number
&\hfil#\hfil\qquad%description
&\hfil#\hfil\enspace
&\hfil#\hfil\cr
&&&&&{\tt INCREASE}\cr
&&&{\tt READ} $a$&4&&&{\tt ZERO}&7&$↑+$\cr
\noalign{\bigskip}
&&&&&{\tt EOF}\cr
\Rightarrow&1&2&&&&6\cr
&&&&&&&&8\cr
&&&{\tt READ} $b$&5&{\tt DECREMENT}&&{\tt NONZERO}\cr}}$$

\bigskip
\bigskip
\bigskip
\bigskip
$$\vcenter{\halign{$\hfil#\hfil$\quad&#\hfil&\hfil#\hfil\qquad%
&\hfil#\hfil\enspace&\hfil#\hfil\cr
&{\tt READ, INCREASE}\cr
\noalign{\bigskip\bigskip}
&&{\tt EOF, ZERO}\cr
\Rightarrow&2&&7&$↑+$\cr
\noalign{\bigskip\bigskip}
&{\tt READ} $b$, {\tt DECREASE}\cr}}$$

\bigskip
\bigskip\noindent
For input $ab$, the trace is shown on the left and the computation on the 
right, for the first program:
$$\vcenter{\halign{$\hfil#\,$&$\hfil#\,$&$\hfil#$\qquad\qquad%
&$\hfil#\hfil$\quad&#\hfil\quad&#\hfil\cr
1,&ab,&0&\langle 1,2\rangle\cr
2,&ab,&0&\langle 2,4\rangle&{\tt READ} $a$\cr
4,&b,&0&\langle 4,2\rangle&&{\tt INCREASE}\cr
2,&b,&1&\langle 2,5\rangle&{\tt READ} $b$\cr
5,&\Lambda,&1&\langle 5,2\rangle&&{\tt DECREASE}\cr
2,&\Lambda,&0&\langle 2,6\rangle&{\tt EOF}\cr
6,&\Lambda,&0&\langle 6,7\rangle&&{\tt ZERO}\cr
7,&\Lambda,&0\cr}}$$
Traces are always longer by one than computations.

Next we define in detail all the types of device we will study.

A {\it control\/} has any finite set, usually called~$Q$, as its carrier.
The repertory consists of all partial functions on~$Q$. Usually, people
use only functions that map some particular $i\in Q$ into some particular
$j\in Q$, and are undefined elsewhere, i.e., functons graphed by
$\{\langle i,j\rangle\}$. Machines have control devices so frequently
that most books include a control device in the definition of a machine.

A {\it finite store\/} has a finite set $F$ as its carrier. If $x$ is the
content of a finite store, the repertory contains $x←a$, i.e., the
constant function $F\times\{a\}$; $x=a$, i.e., the test
$\{\langle a,a\rangle\}$; and the complementary test $x≠a$.

A signed counter has carrier~{\bf Z}. The repertory, where $x$ is the content
of the counter,~is

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
INCREMENT&$\{\langle x,x+1\rangle\}$\cr
DECREMENT&$\{x,x-1\}={\tt INCREMENT}↑{-1}$\cr
ZERO&$\{\langle 0,0\rangle\}$\cr
POSITIVE&$\{\langle x,x\rangle$ where $x>0\}$\cr
NEGATIVE&$\{\langle x,x\rangle$ where $x<0\}$\cr}

\smallskip\noindent
An unsigned counter has carrier~{\bf N}. The repertory is

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
INCREMENT&$\{\langle x,x+1\rangle\}$\cr
DECREMENT&$\{x,x-1\}={\tt INCREMENT}↑{-1}$, defined for $x≥1$\cr
ZERO&$\{\langle 0,0\rangle\}$\cr
NONZERO&$\{\langle x,x\rangle$ where $x≠0\}$\cr
DIMINISH&${\tt DECREMENT}\cup{\tt ZERO}=\{\langle x,\max(x-1,0)\rangle\}$.\cr}

\smallskip\noindent
A (right) stack has carrier $\Sigma↑{\ast}$ for some finite $\Sigma$.
The repertory is (where each~$a$ is a fixed element of~$\Sigma$):

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
PUSH $a$&$\{\langle x,xa\rangle\}$\cr
POP $a$&{\tt PUSH} $a$\cr
${\tt TOP}=a$&$\{\langle xa,xa\rangle\}$\cr
POP&$\bigcup↓a\,${\tt POP} $a$, undefined for $\Lambda$\cr
EMPTY&$\{\langle\Lambda,\Lambda\rangle\}$.\cr}

\smallskip\noindent
A left stack uses the conjugate operations under reflection of the contents.
That is, it operates on the left end of the contents.

A {\it queue\/} has carrier $\Sigma↑{\ast}$ for finite~$\Sigma$. The repertory
(where each~$a$ is a fixed element of~$\Sigma$):

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
APPEND $a$&$\{\langle x,xa\rangle\}$\cr
DELETE $a$&$\{\langle ax,x\rangle\}$\cr
EMPTY&$\{\langle\Lambda,\Lambda\rangle\}$\cr}

\smallskip\noindent
A {\it tape\/} has carrier $\Sigma↑{\ast}\times\Sigma↑{\ast}$ for finite~$\Sigma$.

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
GO RIGHT&$\{\langle x,ay\rangle\,,\,\langle xa,y\rangle\}\cup\{\langle x,\Lambda%
\rangle\,,\,\langle x{\spa},\Lambda\rangle\}$\cr
GO LEFT&is conjugate to {\tt GO RIGHT}\cr
PRINT $a$ RIGHT&$\{\langle x,by\rangle\,,\,\langle x,ay\rangle\}\cup\{\langle
x,\Lambda\rangle\,,\,\langle x,b\rangle\}$\cr
PRINT $a$ LEFT&another  conjugate $\left\{\vcenter{\halign{{\tt #}\hfil\cr
GO LEFT\cr
PRINT $a$ RIGHT\cr
GO RIGHT\cr}}\right\}$\cr
$a$ ON RIGHT&$\{\langle x,ay\rangle\,,\,\langle x,ay\rangle\}\quad a≠\spa$\cr
$\spa$ ON RIGHT&$\{\langle x,{\spa}y\rangle\,,\,\langle x,{\spa}y\rangle\}\cup
\{\langle x,\Lambda\rangle\,,\,\langle x,\Lambda\rangle\}$.\cr}

\smallskip\noindent
An {\it input\/} has carrier $\Sigma↑{\ast}\times\Sigma↑{\ast}$.

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
SCAN $a$&$\{\langle x,ay\rangle\,,\,\langle xa,y\rangle\}$\cr
EOF&$\{\langle x,\Lambda\rangle\,,\,\langle x,\Lambda\rangle\}$\cr}

\smallskip\noindent
An {\it output\/} has carrier $\Sigma↑{\ast}$:

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\qquad&#\hfil\cr
PRINT $a$&$\{x,xa\}$.\cr}

\bigskip
\parindent0pt
\copyright 1988 Robert W. Floyd

First draft April 4, 1988.

\bye